package com.chentf.algorithm.algorithm.StringAndArrays;

import java.lang.reflect.Array;
import java.util.Arrays;
import java.util.Map;
import java.util.function.Function;
import java.util.stream.Collectors;

/**
 * 多数元素
 * 给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
 * 你可以假设数组是非空的，并且给定的数组总是存在多数元素。
 * 示例 1：
 * 输入：nums = [3,2,3]
 * 输出：3
 *
 * 示例 2：
 * 输入：nums = [2,2,1,1,1,2,2]
 * 输出：2
 */
public class majorityElement {

    /**
     * 计数法
     * 遍历整个数组，对记录每个数值出现的次数(利用 HashMap，其中 key 为数值，value 为出现次数)；
     * 接着遍历 HashMap 中的每个 Entry，寻找 value 值> nums.length / 2 的 key 即可。
     * @param nums
     * @return
     */
    public static int majorityElement01(int[] nums){
        // 使用了流(Streams)来将一个整数数组(nums)转换为一个Map<Integer, Long>，该映射表表示数组中每个整数出现的频次
        Map<Integer, Long> map = Arrays.stream(nums).boxed().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
        long limit = nums.length >> 1;
        for(Map.Entry<Integer, Long> entry : map.entrySet()){
            if(entry.getValue() > limit) {
                return entry.getKey();
            }
        }
        return -1;
    }

    /**
     * 排序法:
     * 既然数组中有出现次数 > ⌊ n/2 ⌋ 的元素，那排好序之后的数组中，相同元素 总是 相邻 的。
     * 即存在长度 > ⌊ n/2 ⌋ 的一长串 由 相同元素 构成的 连续子数组。
     * 举个例子：
     * 无论是 1 1 1 2 3，0 1 1 1 2 还是 -1 0 1 1 1，数组中间的元素总是“多数元素”，毕竟它长度 > ⌊ n/2 ⌋。
     * @param nums
     * @return
     */
    public static int majorityElement02(int[] nums){
        Arrays.sort(nums);
        return nums[nums.length >> 1];
    }

    /**
     * 投票发（同归于尽法）
     * 假设将每种大小的数字划分为一个阵营，阵营之间决出最终的胜利者。且只能1换1。
     * 题目中给出，多数一定超过总数的一半。那么不管队伍之间怎么厮杀，人数最多的一定会留到最后。
     * 第一个进入战场的士兵，直接占领高地，那么此时胜利者是这个阵营的人，现存兵力count = 1。
     * 接下来，每次进入战场一个士兵。
     * （1）如果该士兵和占领高地的士兵是一个阵营，则集合到一起，胜利者不变，现存兵力count++。
     * （2）如果该士兵和占领高地的士兵不是一个阵营，那么会和占领阵营的士兵同归于尽，此时剩余兵力count--，此时即使双方全部战死，也不会变更胜利者，因为双方都没有人了。
     * （3）当该士兵发现战场上没有任何士兵，那么他将占领高地，胜利者为该阵营，此时兵力count = 1
     * 或者count++（因为此时兵力为0）。
     * 就这样一直到最后，知道少数人的阵营全部阵亡，那么剩下的几个必然是属于多数阵营，胜利者就是他们。
     * @param nums
     * @return
     */
    public static int majorityElement03(int[] nums){
        int win = nums[0];
        int count = 1;
        for (int i = 1; i < nums.length; i++) {
            if(nums[i] == win){
                count++;
            }else if(count == 0){
                win = nums[i];
                count = 1;
            }else {
                count --;
            }
        }
        return win;
    }

    public static void main(String[] args) {
        int[] nums = {2,2,1,1,1,2,2};
        System.out.println(majorityElement01(nums));
        System.out.println(majorityElement02(nums));
        System.out.println(majorityElement03(nums));
    }
}
